#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <math.h>
#include <time.h>
#include <sstream>
#include <cstdlib>

#include "cell.h"
#include "nodes.h"

using namespace std;

typedef int LineCounterType; // used to read in file and keep track of line
typedef vector<vector<CellType> > GridType;  //index of cell at this location
typedef vector<TrunkNode> ChannelRowType;
typedef vector<ChannelRowType> ChannelType;
typedef multimap<CellType, CellType> VCGmap;
typedef map<CellType, CellType> NetlistType;

// cell grid:
//       x
//    0  1  2
// y  1  
//    2
// 
// contains cellNum, cost: -1 if empty location

class Grid {
public:
	CellType n; // number of cells total
	CellType squareSide;  //Length of one side of the square grid that holds cells
	// Placement Variables
	GridType cellGrid;  //Grid of cellNums as reference in vector of cells, as well as cost in that location/position
	vector<Cell> cells;  // master cell list
	vector<CostType> costs;
	CostType totalCost;
	// Router Variables
	vector<CellType> feedthrough; // keeps track of feedthroughs per row
	CostType totalFeedthrough;  // total feedthroughs
	CellType maxFeedthrough;  // number of feedthroughs in row needing the most
	CellType middleFeedStart; // location that middle feeds will start at
	CellType middleFeeds;  // number of feedthroughs to have stacked in middle
	CellType terminalRowSize; // number of terminals in a row
	map<CellType,TerminalNode> feedthroughList; // maps of nets with feedthrough, key=netNum, data=TerminalNode
	vector<pair<vector<TerminalNode>,vector<TerminalNode> > > routeTerminals; //vector of pairs of vectors representing top/bottom of channel
	vector<ChannelType> routeChannels; // vectors representing channels being routed in (netnum, start, end)
	vector<VCGmap> VCG; //vertical constraints graph for each channel
	vector<NetlistType> routeNetlist; // list of nets to be routed for each channel

	string newFile; // filename of mag file to be made

	Grid(const char* netlist_file) {
		// use resize function to make square out of cells grid
        CellType a, b, c, d, e = 0;  // NetNum, CellNum TerminalNum CellNum TerminalNum
		double sqrRootCompare;
		int phase = 0;
		string line;
		LineCounterType lineNumber = 0;
		// convert char* to string for output
		stringstream ss;
		ss << netlist_file;
		ss >> newFile;
		ifstream infile(netlist_file);
		if (!infile.is_open()) {
			cerr << "Cannot open netlist_file: " << netlist_file << endl;
			exit(1);
		}
		else {
			while (infile.good()) {
				getline(infile,line);
				lineNumber++; //Keeps track of line number for error output
				if (phase == 0) {
					// First line of file, should contain number of cells
					if(sscanf(line.c_str(),"%hd",&n) == EOF) {
						cerr << "Number of cells missing at start of netlist." << endl;
						exit(1);
					}
					cerr << "Cells: " << n << endl;
					cells.resize(n);
					costs.resize(n);
					//cells.assign(n, Cell());
					// size the square grid correctly
					squareSide = (CellType)sqrt((double)n);
					sqrRootCompare = sqrt((double)n);
					if(squareSide != sqrRootCompare) {
						squareSide++;
					}
					// BOZO: experiment with making the square a little bigger
			//		squareSide+=10;
					feedthrough.resize(squareSide);
					feedthrough.assign(squareSide, 0);
					cellGrid.resize(squareSide);
					for(short int i = 0; i < squareSide; i++) {
						cellGrid[i].resize(squareSide);
						cellGrid[i].assign(squareSide, -1);
					}
					totalCost = 0;
					phase = 1;
				}
				else if (phase == 1) {
					// This line contains number of nets, does not necessarily matter
                    phase = 2;
				}
				else if (phase == 2) {
					// Line contains one net
					// BOZO: check for faulty net?
					if(sscanf(line.c_str(),"%hd %hd %hd %hd %hd",&a,&b,&c,&d,&e) == EOF) {
						cerr << "Ignoring netlist line: " << lineNumber << ", content: " << line << endl;
						break;
					}
					else {
						//cellNum and terminalNum starting at 1
						// first item, net number, ignored
						a--; // netNum
						b--; //first cellNum
						c--; // first cellTerm
						d--; // second cellNum
						e--; // second cellTerm
						cells[b].addConnection(c,d,e,a);
						cells[d].addConnection(e,b,c,a);
					}
				}
				else {
					cerr << "Invalid netlist, phase !=0|1|2 reached!" << phase << endl;
					exit(1);
				}
			}
			infile.close();
		}
	}

// Placer Functions
	CostType initialCost();
	void feedthroughCalc();
	void vertHeightCalc(CellType index, CellType j, CellType k, PositionType &start, PositionType &end, bool &dir, CellType &startCell);
	CostType cellCost(CellType index, bool swapTest, PositionType x = 0, PositionType y = 0, bool flip = false);
	void swap(PositionType x0, PositionType y0, PositionType x1, PositionType y1, bool flip0, bool flip1);
	void updateCost(CellType index);
	CostType swapCostImprove(PositionType x0, PositionType y0, PositionType x1, PositionType y1, bool &flip0, bool &flip1);
	void optimizePlace();
	void initialPlace();
	void place();

// Router Functions
	void initializeRouter();
	void initCellTerms(CellType index, CellType i, CellType &j);
	void addFeedthrough(CellType cellRow, CellType &cellCol);
	void initializeFeedthroughs();
	CellType chooseFeedthroughCell(CellType preferIndex, PositionType cellRow, bool dir);
	CellType routeIndex(CellType index);
	void createVCG(CellType index);
	CellType rowFit(CellType channel, PositionType start, PositionType end);
	void calcNet(CellType channel, CellType netNum, PositionType &start, PositionType &end, bool &start_up, bool &end_up);
	CellType nextNet(CellType channel);
	void router();
	void route();

// Print to Magic File

	void printMag() {
		// prints out the magic file
		// metal1 is horizontal, metal2 is vertical
		vector<MagicWire> metal1;
		vector<MagicWire> metal2;
		vector<MagicWire> m2contact;
		vector<MagicCell> magicCells;
		vector<MagicCell> labels;
		CellType currentX = 0, currentY = 0, topY = 0, bottomY = 0; // keeps track of current x/y position, and top/bottom of current channel
		CellType maxX, numberVias = 0; // number of Vias
		
		for(short int i = squareSide; i >= 0; i--) { // for each channel in reverse order
			// calculate the width of the channel
			// (# rows in channel * 2) + 1
			CellType channelWidth = (routeChannels[i].size()*2);
			currentX = 0; // reset X to left side again
			bottomY = currentY;
			currentY++;
			topY = currentY + channelWidth;

			// insert channel trunks/branches
			for(unsigned short int j = 0; j < routeChannels[i].size(); j++) { // for each row in the channel
				// BOZO: might want to do this in reverse order
				for(unsigned short int k = 0; k < routeChannels[i][j].size(); k++) { // for each trunk in row
					CellType m1_xb, m1_xt, m2_yb, m2_yt;
					m1_xb = magChannelX(routeChannels[i][j][k].start);
					m1_xt = magChannelX(routeChannels[i][j][k].end)+1;
					// insert metal1
					metal1.push_back(MagicWire(m1_xb, currentY, m1_xt, currentY+1));
					// insert metal2 for start and end
					if(routeChannels[i][j][k].start_up) {
						m2_yt = topY;
						m2_yb = currentY;
					}
					else {
						m2_yt = currentY;
						m2_yb = bottomY;
					}
					// BOZO: this will not always overlap full m2, but m2contact will cover up
					metal2.push_back(MagicWire(m1_xb, m2_yb, m1_xb+1, m2_yt));
					if(routeChannels[i][j][k].end_up) {
						m2_yt = topY;
						m2_yb = currentY;
					}
					else {
						m2_yt = currentY;
						m2_yb = bottomY;
					}
					metal2.push_back(MagicWire(m1_xt-1, m2_yb, m1_xt, m2_yt));
					// insert m2contact
					if(m1_xb != m1_xt-1) {
						m2contact.push_back(MagicWire(m1_xb, currentY, m1_xb+1, currentY+1));
						m2contact.push_back(MagicWire(m1_xt-1, currentY, m1_xt, currentY+1));
						numberVias+=2;
					}
					// insert label
					labels.push_back(MagicCell(routeChannels[i][j][k].netNum, m1_xb, currentY, false));
				}
				currentY += 2;
			}

			currentX = 0; // reset X to left side again

			// insert cells
			if( i != 0) {
				metal2.push_back(MagicWire(currentX, currentY, currentX+1, currentY+6));
				currentX += 2;
				for(CellType j = 0; j <= middleFeedStart; j++) { // first set of alternating cells/feedthroughs
					// add cell
					if(cellGrid[i-1][j] != -1) {
						// cell is a real cell
						// BOZO: does not mirror cells
						magicCells.push_back(MagicCell(cellGrid[i-1][j], currentX, currentY, false));
					}
					currentX += 7;
					// put in feedthrough wire
					metal2.push_back(MagicWire(currentX, currentY, currentX+1, currentY+6));
					currentX += 2;
				}
				// put in middle feedthroughs
				for(CellType j = 0; j < middleFeeds; j++) {
					metal2.push_back(MagicWire(currentX, currentY, currentX+1, currentY+6));
					currentX += 2;
				}
				// put in cells after feedthrough
				for(CellType j = middleFeedStart+1; j < squareSide; j++) {
					// add cell
					if(cellGrid[i-1][j] != -1) {
						// cell is a real cell
						// BOZO: does not mirror cells
						magicCells.push_back(MagicCell(cellGrid[i-1][j], currentX, currentY, false));
					}
					currentX += 7;
					// put in feedthrough wire
					metal2.push_back(MagicWire(currentX, currentY, currentX+1, currentY+6));
					currentX += 2;
				}
				maxX = currentX;
			}
			currentY += 6;  // insert a space between cells and channel wires
		}
		cerr << "Bounding Box Dimensions: " << maxX-2 << "x" << currentY-6 << endl;
		cerr << "Bounding Box Area: " << (maxX-2)*(currentY-6) << endl;
		cerr << "Total Vias: " << numberVias << endl;

		ofstream myfile;

		// get the correct filename
		newFile.erase(newFile.end()-3, newFile.end());
		newFile.erase(newFile.begin(), newFile.begin()+9);
		newFile.erase(newFile.begin()+1, newFile.begin()+10);
		newFile = "Layout"+newFile+"mag";
		cerr << "Output File: " << newFile << endl;
		myfile.open (newFile.c_str());
		if (!myfile.is_open()) {
			cerr << "Cannot open magic file: " << newFile << endl;
			cerr << "You might need to create the \"Layout\" folder." << endl;
			exit(1);
		}
		myfile << "magic\n";
		myfile << "tech nmos\n";
		myfile << "timestamp " << time(0) << "\n";
		myfile << "<< metal1 >>\n";
		for(unsigned short int i = 0; i < metal1.size(); i++) {
			myfile << "rect " << metal1[i].position[0] << " " << metal1[i].position[1] << " " << metal1[i].position[2] << " " << metal1[i].position[3] << "\n";
		}
		myfile << "<< m2contact >>\n";
		for(unsigned short int i = 0; i < m2contact.size(); i++) {
			myfile << "rect " << m2contact[i].position[0] << " " << m2contact[i].position[1] << " " << m2contact[i].position[2] << " " << m2contact[i].position[3] << "\n";
		}
		myfile << "<< metal2 >>\n";
		for(unsigned short int i = 0; i < metal2.size(); i++) {
			myfile << "rect " << metal2[i].position[0] << " " << metal2[i].position[1] << " " << metal2[i].position[2] << " " << metal2[i].position[3] << "\n";
		}
		for(unsigned short int i = 0; i < magicCells.size(); i++) {
			myfile << "use cell  cell_" << magicCells[i].cellNum << "\n";
			myfile << "timestamp " << time(0) << "\n";
			if(magicCells[i].mirror) {
				// cell is upside down
				myfile << "transform 1 0 " << magicCells[i].posX << " 0 -1 " << magicCells[i].posY+6 << "\n";
			}
			else {
				myfile << "transform 1 0 " << magicCells[i].posX << " 0 1 " << magicCells[i].posY << "\n";
			}
			myfile << "box 1 0 5 6\n";
		}
		myfile << "<< labels >>\n";
		for(unsigned short int i = 0; i < labels.size(); i++) {
			myfile << "rlabel m2contact " << labels[i].posX << " " << labels[i].posY << " " << labels[i].posX << " " << labels[i].posY << " 0 " << labels[i].cellNum << "\n";
		}
		myfile << "<< end >>\n";
		myfile.close();
	}

	CellType magChannelX(CellType X) {
		// returns the beginning magic X coordinate for an X coordinate in channel array
		// metal widths of 1
		// can either be: before middle feeds, in middle feeds, after middle feeds
		// before middle feeds
		// in middle feeds
		// after middle feeds
		CellType indexMiddleFeedStart, indexMiddleFeedEnd;
		indexMiddleFeedStart = (3*middleFeedStart)+3; // first middle feed is this index
		indexMiddleFeedEnd = indexMiddleFeedStart + middleFeeds; // last middle feed index
		
		if(X < indexMiddleFeedStart) {
			return X*3;
		}
		else if ((X >= indexMiddleFeedStart) && (X <= indexMiddleFeedEnd)) {
			return (indexMiddleFeedStart*3)+2*(X-indexMiddleFeedStart);
		}
		else if (X > indexMiddleFeedEnd) {
		//	CellType subtract = -2;
		//	if(middleFeeds > 1) {
		//		subtract = middleFeeds - 1;
		//	}
			return (X*3)-(middleFeeds);
		}
		else {
			// a terminal outside range was given
			return -1;
		}

	}

	CellType magCellX(CellType X) {
		// returns the beginning magic X coordinate for an X coordinate in cellGrid

		CellType indexMiddleFeedStart, indexMiddleFeedEnd;
		indexMiddleFeedStart = (3*middleFeedStart)+3; // first middle feed is this index
		indexMiddleFeedEnd = indexMiddleFeedStart + middleFeeds; // last middle feed index
		
		if(X < indexMiddleFeedStart) {
			return X*3;
		}
		else if ((X >= indexMiddleFeedStart) && (X <= indexMiddleFeedEnd)) {
			return (indexMiddleFeedStart*3)+2*(X-indexMiddleFeedStart);
		}
		else if (X > indexMiddleFeedEnd) {
			return (X*3)-(middleFeeds-2);
		}
		else {
			// a terminal outside range was given
			return -1;
		}

	}

// Console printing functions
	void prettyPrint() {
		cerr << "Number of Cells: " << n << " Square Side: " << squareSide << endl;
		for(unsigned int i = 0; i < cells.size(); i++) {
                cerr << "Cell Number: " << i << endl;
		        cells[i].prettyPrint();
		}
	}

	void prettyPrintGrid() {
		cerr << "Grid:" << endl;
		for(CellType i = 0; i < squareSide; i++) {
			for(CellType j = 0; j < squareSide; j++) {
				CostType cost;
				if (cellGrid[i][j] != -1) {
					cost = cells[cellGrid[i][j]].cost;
				}
				else {
					cost = 0;
				}
				cerr << cellGrid[i][j] << "," << cost << " ";
			}
			cerr << endl;
		}
	}

	void prettyPrintRouteGrid() {
		cerr << "Channel Layout:" << endl;
		for(unsigned short int i = 0; i < routeTerminals.size(); i++) { // for each channel
			for(unsigned short int j = 0; j < routeTerminals[i].first.size(); j++) { // for each terminal
				// print top of channel
				if(routeTerminals[i].first[j].netNum >= 0) {
					cerr << " ";
				}
				cerr << routeTerminals[i].first[j].netNum << " ";
			}
			cerr << endl;
			cerr << endl;
			for(unsigned short int j = 0; j < routeTerminals[i].first.size(); j++) { // for each terminal
				// print bottom of channel
				if(routeTerminals[i].second[j].netNum >= 0) {
					cerr << " ";
				}
				cerr << routeTerminals[i].second[j].netNum << " ";
			}
			cerr << endl;
		}

	}

	void prettyPrintRouteChannel() {
		cerr << "Trunks in Channels:" << endl;
		for(unsigned short int i = 0; i < routeChannels.size(); i++) { // for each channel
			cerr << "Channel: " << i << endl;
			for(unsigned short int j = 0; j < routeChannels[i].size(); j++) { // for each row in channel
				cerr << "  Row: " << j << endl;
				for(unsigned short int k = 0; k < routeChannels[i][j].size(); k++) { // for each trunk in row
					cerr << "    Net:   " << routeChannels[i][j][k].netNum << endl;
					cerr << "    Start: " << routeChannels[i][j][k].start << "  Up: " << routeChannels[i][j][k].start_up << endl;
					cerr << "    End:   " << routeChannels[i][j][k].end << "  Up: " << routeChannels[i][j][k].end_up << endl;
				}
			}
		}
	}
};
